package com.lw.leetcode.str.b;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 792. 匹配子序列的单词数
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/16 21:31
 */
public class NumMatchingSubseq {

    public static void main(String[] args) {
        NumMatchingSubseq test = new NumMatchingSubseq();

        // 3
//        String str = "abcde";
//        String[] arr = {"a", "bb", "acd", "ace"};

        // 5
        String str = "rwpddkvbnnuglnagtvamxkqtwhqgwbqgfbvgkwyuqkdwhzudsxvjubjgloeofnpjqlkdsqvruvabjrikfwronbrdyyjnakstqjac";
        String[] arr = {"wpddkvbnn","lnagtva","kvbnnuglnagtvamxkqtwhqgwbqgfbvgkwyuqkdwhzudsxvju","rwpddkvbnnugln","gloeofnpjqlkdsqvruvabjrikfwronbrdyyj","vbgeinupkvgmgxeaaiuiyojmoqkahwvbpwugdainxciedbdkos","mspuhbykmmumtveoighlcgpcapzczomshiblnvhjzqjlfkpina","rgmliajkiknongrofpugfgajedxicdhxinzjakwnifvxwlokip","fhepktaipapyrbylskxddypwmuuxyoivcewzrdwwlrlhqwzikq","qatithxifaaiwyszlkgoljzkkweqkjjzvymedvclfxwcezqebx"};

        int i = test.numMatchingSubseq(str, arr);
        System.out.println(i);
    }


    public int numMatchingSubseq(String s, String[] words) {
        Map<Character, List<String>> map = new HashMap<>(26, 1);
        for (String word : words) {
            map.computeIfAbsent(word.charAt(0), v -> new ArrayList<>()).add(word);
        }
        int count = 0;
        for (char c : s.toCharArray()) {
            List<String> list = map.get(c);
            if (list == null) {
                continue;
            }
            List<String> li = new ArrayList<>();
            for (String str : list) {
                if (str.length() == 1) {
                    count++;
                    continue;
                }
                char item = str.charAt(1);
                if (item == c) {
                    li.add(str.substring(1));
                } else {
                    map.computeIfAbsent(item, v -> new ArrayList<>()).add(str.substring(1));
                }
            }
            map.put(c, li);
        }
        return count;
    }

}
